package com.xie.leetcode.array;

//15. 三数之和
//        给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
//
//        注意：答案中不可以包含重复的三元组。
//
//
//
//        示例 1：
//
//        输入：nums = [-1,0,1,2,-1,-4]
//        输出：[[-1,-1,2],[-1,0,1]]
//        示例 2：
//
//        输入：nums = []
//        输出：[]
//        示例 3：
//
//        输入：nums = [0]
//        输出：[]
//
//
//        提示：
//
//        0 <= nums.length <= 3000
//        -105 <= nums[i] <= 105

import java.util.*;

/**
 * @author xiezhendong
 * @date 2021/10/30
 */
public class ThreeSum {

    public static void main(String[] args) {
        ThreeSum threeSum = new ThreeSum();
        System.out.println(threeSum.threeSum(new int[]{-1, 0, 1, 2, -1, -4}));
        System.out.println(threeSum.threeSum(new int[]{}));
        System.out.println(threeSum.threeSum(new int[]{0}));
    }

    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> threeSumList = new ArrayList<>();
        if (nums == null || nums.length < 3) {
            return threeSumList;
        }
        Set<String> intsSet = new HashSet<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                break;
            }
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            for (int j = 0; j < nums.length; j++) {
                if (j > 0 && nums[j] == nums[j - 1]) {
                    continue;
                }
                for (int k = 0; k < nums.length; k++) {
                    if (k > 0 && nums[k] == nums[k - 1]) {
                        continue;
                    }
                    if (i != j && i != k && j != k) {
                        if (nums[i] + nums[j] + nums[k] == 0) {
                            int[] ints = new int[]{nums[i], nums[j], nums[k]};
                            Arrays.sort(ints);
                            String str = ints[0] + ";" + ints[1] + ";" + ints[2];
                            if (!intsSet.contains(str)) {
                                intsSet.add(str);
                                List<Integer> integerList = new ArrayList<>();
                                for (int anInt : ints) {
                                    integerList.add(anInt);
                                }
                                threeSumList.add(integerList);
                            }
                        }
                    }
                }
            }
        }

        return threeSumList;
    }

    /**
     * 双指针
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum1(int[] nums) {
        List<List<Integer>> threeSumList = new ArrayList<>();
        if (nums == null || nums.length < 3) {
            return threeSumList;
        }
        Arrays.sort(nums);
        int len = nums.length;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                break;
            }
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int lIndex = i + 1;
            int rIndex = len - 1;
            while (lIndex < rIndex) {
                int sum = nums[i] + nums[lIndex] + nums[rIndex];
                if (sum == 0) {
                    threeSumList.add(Arrays.asList(nums[i], nums[lIndex], nums[rIndex]));
                    while (lIndex < rIndex && nums[lIndex] == nums[lIndex + 1]) {
                        lIndex++;
                    }
                    while (lIndex < rIndex && nums[rIndex] == nums[rIndex - 1]) {
                        rIndex--;
                    }
                    lIndex++;
                    rIndex--;
                } else if (sum < 0) {
                    lIndex++;
                } else {
                    rIndex--;
                }
            }
        }

        return threeSumList;
    }
}
